package 剑指offer.全排列;

import java.util.Arrays;


public class 输出0到N的全排列 {

    /*
    给定一个数 N，输出 0 到 N 的全部数据

    解答：考的是是否注意到现有的数据类型会溢出

    因此需要使用字符串处理，字符串不会溢出
     */
    public static void print0ToN(String str) {
        // 首先确定需要打印的数最高是几位数
        String[] numbers = new String[str.length()];
        Arrays.fill(numbers, "0");
        // 然后从高位开始填充 0，在地位上输出 0~9，低位输出一次结束后，递归回来高位填充 1，然后低位再输出一次
        for (int i = 0; i < 10; i++) {
            numbers[0] = i + "";
            // 使用递归函数给低位填充数字
            addNumberToLowIndex(numbers, 0, str);
        }
    }

    // 检查目前的数据是否超过 str 了，超过了就不需要做全排列了
    public static boolean checkNumberIsEnough(String[] numbers, String str) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < numbers.length; i++) {
            builder.append(numbers[i]);
        }
        return builder.toString().compareTo(str) > 0 ? true : false;
    }

    /**
     * 在低位上做轮询，高位每变更一次低位就从0到9填充一次
     *
     * @param number 需要填充的数组
     * @param index  填充哪一位
     */
    public static void addNumberToLowIndex(String[] number, int index, String str) {
        // 设置递归函数返回的条件
        if (index == number.length - 1) {
            // 打印当前的数组
            print(number);
            return;
        }
        for (int i = 0; i < 10; i++) {
            number[index + 1] = i + "";
            if (!checkNumberIsEnough(number, str)) { // 必须先确保 number 里面存储的数据小于等于 str 表示的数据的时候才能遍历，否则算法结束

                // 往更低位填充
                addNumberToLowIndex(number, index + 1, str);
            } else {
                break;
            }
        }
    }

    public static void print(String[] number) {
        for (int i = 0; i < number.length; i++) {
            System.out.print(number[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        String str = "568461235798465";
        String str = "56";
        print0ToN(str);

//        System.out.println("10".compareTo("11"));
    }
}
